{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Map of Highest Peak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: highestPeak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #地图中的最高点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为&nbsp;<code>m x n</code>&nbsp;的整数矩阵&nbsp;<code>isWater</code>&nbsp;，它代表了一个由 <strong>陆地</strong>&nbsp;和 <strong>水域</strong>&nbsp;单元格组成的地图。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>isWater[i][j] == 0</code>&nbsp;，格子&nbsp;<code>(i, j)</code>&nbsp;是一个 <strong>陆地</strong>&nbsp;格子。</li>\n",
    "\t<li>如果&nbsp;<code>isWater[i][j] == 1</code>&nbsp;，格子&nbsp;<code>(i, j)</code>&nbsp;是一个 <strong>水域</strong>&nbsp;格子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要按照如下规则给每个单元格安排高度：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个格子的高度都必须是非负的。</li>\n",
    "\t<li>如果一个格子是 <strong>水域</strong>&nbsp;，那么它的高度必须为 <code>0</code>&nbsp;。</li>\n",
    "\t<li>任意相邻的格子高度差 <strong>至多</strong>&nbsp;为 <code>1</code>&nbsp;。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）</li>\n",
    "</ul>\n",
    "\n",
    "<p>找到一种安排高度的方案，使得矩阵中的最高高度值&nbsp;<strong>最大</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个大小为&nbsp;<code>m x n</code>&nbsp;的整数矩阵 <code>height</code>&nbsp;，其中 <code>height[i][j]</code>&nbsp;是格子 <code>(i, j)</code>&nbsp;的高度。如果有多种解法，请返回&nbsp;<strong>任意一个</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82045-am.png\" style=\"width: 220px; height: 219px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>isWater = [[0,1],[0,0]]\n",
    "<b>输出：</b>[[1,0],[2,1]]\n",
    "<b>解释：</b>上图展示了给各个格子安排的高度。\n",
    "蓝色格子是水域格，绿色格子是陆地格。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82050-am.png\" style=\"width: 300px; height: 296px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>isWater = [[0,0,1],[1,0,0],[0,0,0]]\n",
    "<b>输出：</b>[[1,1,0],[0,1,1],[1,2,2]]\n",
    "<b>解释：</b>所有安排方案中，最高可行高度为 2 。\n",
    "任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == isWater.length</code></li>\n",
    "\t<li><code>n == isWater[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>isWater[i][j]</code>&nbsp;要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code>&nbsp;。</li>\n",
    "\t<li>至少有 <strong>1</strong>&nbsp;个水域格子。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [map-of-highest-peak](https://leetcode.cn/problems/map-of-highest-peak/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [map-of-highest-peak](https://leetcode.cn/problems/map-of-highest-peak/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,0]]', '[[0,0,1],[1,0,0],[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\r\n",
    "        m, n = len(isWater), len(isWater[0])\r\n",
    "        q = [(i, j) for i in range(len(isWater)) for j in range(len(isWater[0])) if isWater[i][j]]\r\n",
    "        step = 0\r\n",
    "        vis = [[False]* n for _ in range(m)]\r\n",
    "        for x, y in q:\r\n",
    "            vis[x][y] = True \r\n",
    "        while q:\r\n",
    "            tmp = q \r\n",
    "            q = []\r\n",
    "            for x, y in tmp:\r\n",
    "                isWater[x][y] = step\r\n",
    "                for nx, ny in (x + 1,y), (x, y + 1), (x - 1, y), (x, y - 1):\r\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\r\n",
    "                        q.append((nx, ny)) \r\n",
    "                        vis[nx][ny] = True \r\n",
    "            step += 1\r\n",
    "        return isWater\r\n",
    "                    \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        queue, m, n, cost = [], len(isWater), len(isWater[0]), 0\n",
    "        for i, row in enumerate(isWater):\n",
    "            for j, val in enumerate(row):\n",
    "                # 水域，作为起点入队，并更新为答案需要返回的0\n",
    "                if val:\n",
    "                    isWater[i][j] = 0\n",
    "                    queue.append((i, j))\n",
    "                # 陆地：先更新为无限大的高度，等BFS时更新它\n",
    "                else:\n",
    "                    isWater[i][j] = inf\n",
    "        while queue:\n",
    "            nxt = []\n",
    "            cost += 1\n",
    "            for i, j in queue:\n",
    "                for dx, dy in (0, 1), (1, 0), (-1, 0), (0, -1):\n",
    "                    # 只有没被更新过的陆地才能被更新，否则已经有更近的水域访问过它了\n",
    "                    if 0 <= (nx := i + dx) < m and 0 <= (ny := j + dy) < n and isWater[nx][ny] > cost:\n",
    "                        isWater[nx][ny] = cost\n",
    "                        nxt.append((nx, ny))\n",
    "            queue = nxt\n",
    "        return isWater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "      m, n = len(isWater), len(isWater[0])\n",
    "      ans = [[0] * n for _ in range(m)]\n",
    "      stack = []\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          if isWater[i][j]:\n",
    "            isWater[i][j] = -1\n",
    "            stack.append((i, j))\n",
    "        \n",
    "      Dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "      h = 1\n",
    "      while stack:\n",
    "        temp = []\n",
    "        for x, y in stack:\n",
    "          for dx, dy in Dir:\n",
    "            X, Y = x + dx, y + dy\n",
    "            if 0 <= X < m and 0 <= Y < n and isWater[X][Y] == 0:\n",
    "              temp.append((X, Y))\n",
    "              ans[X][Y] = h\n",
    "              isWater[X][Y] = -1\n",
    "        h += 1\n",
    "        stack = temp\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1: \n",
    "                    queue.append([i, j])\n",
    "                else:\n",
    "                    res[i][j] = -1\n",
    "        step = 1\n",
    "        while len(queue) != 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cn = queue.popleft()\n",
    "                for each_dir in dirs:\n",
    "                    nx, ny = cn[0] + each_dir[0], cn[1] + each_dir[1]\n",
    "                    if 0 <= nx < m and 0 <= ny < n and res[nx][ny] == -1:\n",
    "                        res[nx][ny] = step\n",
    "                        queue.append([nx, ny])\n",
    "            step += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        d = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    d.append((i, j))\n",
    "                ans[i][j] = 0 if isWater[i][j] else -1\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        h = 1\n",
    "        while d:\n",
    "            k = len(d)\n",
    "            for _ in range(k):\n",
    "                x, y = d.popleft()\n",
    "                for di in dirs:\n",
    "                    nx = x + di[0]\n",
    "                    ny = y + di[1]\n",
    "                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:\n",
    "                        ans[nx][ny] = h\n",
    "                        d.append((nx, ny))\n",
    "            h += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        height = [[-1]*n for _ in range(m)]\n",
    "        \n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]==1:\n",
    "                    height[i][j] = 0\n",
    "                    q.append((i,j))\n",
    "\n",
    "        level = 1\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for x,y in tmp:\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and height[nx][ny]==-1:\n",
    "                        height[nx][ny]=level\n",
    "                        q.append((nx,ny))\n",
    "            level += 1\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        # 因为水的高度一定是0，以水为源点做多源BFS，逐渐升高高度即可\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        height = [[-1]*n for _ in range(m)]\n",
    "        \n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]==1:\n",
    "                    height[i][j] = 0\n",
    "                    q.append((i,j))\n",
    "\n",
    "        level = 1\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for x,y in tmp:\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and height[nx][ny]==-1:\n",
    "                        height[nx][ny]=level\n",
    "                        q.append((nx,ny))\n",
    "            level += 1\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        d = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    d.append((i, j))\n",
    "                ans[i][j] = 0 if isWater[i][j] else -1\n",
    "\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        h = 1\n",
    "        while d:\n",
    "            size = len(d)\n",
    "            for _ in range(size):\n",
    "                x, y = d.popleft()\n",
    "                for di in dirs:\n",
    "                    nx, ny = x + di[0], y + di[1]\n",
    "                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:\n",
    "                        ans[nx][ny] = h\n",
    "                        d.append((nx, ny))\n",
    "            h += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        d = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    d.append((i, j))\n",
    "                ans[i][j] = 0 if isWater[i][j] else -1\n",
    "\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        h = 1\n",
    "        while d:\n",
    "            size = len(d)\n",
    "            for _ in range(size):\n",
    "                x, y = d.popleft()\n",
    "                for di in dirs:\n",
    "                    nx, ny = x + di[0], y + di[1]\n",
    "                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:\n",
    "                        ans[nx][ny] = h\n",
    "                        d.append((nx, ny))\n",
    "            h += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        d = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    d.append((i, j))\n",
    "                ans[i][j] = 0 if isWater[i][j] else -1\n",
    "\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        h = 1\n",
    "        while d:\n",
    "            size = len(d)\n",
    "            for _ in range(size):\n",
    "                x, y = d.popleft()\n",
    "                for di in dirs:\n",
    "                    nx, ny = x + di[0], y + di[1]\n",
    "                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:\n",
    "                        ans[nx][ny] = h\n",
    "                        d.append((nx, ny))\n",
    "            h += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        #max_gap:1\n",
    "        # bfs求到达边界时的max_len\n",
    "        max_len = 0\n",
    "        q = deque()\n",
    "        m,n = len(isWater), len(isWater[0])\n",
    "        grid = [[-1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    q.append((i,j))\n",
    "                    grid[i][j] = 0\n",
    "\n",
    "        #vis = set()\n",
    "        step = 0\n",
    "        dirs = [[-1,0], [1,0], [0,1], [0,-1]]\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                i,j = q.popleft()\n",
    "                #vis.add((i,j)) #可以不用这个\n",
    "                for d1,d2 in dirs:\n",
    "                    x,y = i+d1, j+d2\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y] == -1: #未访问过的陆地\n",
    "                        q.append((x,y))\n",
    "                        grid[x][y] = step \n",
    "\n",
    "        return grid\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        q = queue.deque()\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "        if m == 0:\n",
    "            return isWater\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    q.append((i,j))\n",
    "                isWater[i][j] = -1 #unvisited\n",
    "\n",
    "        depth = 0\n",
    "        while len(q) != 0:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                row, col = q.popleft()\n",
    "                if row < 0 or row >= m or col < 0 or col >= n \\\n",
    "                or isWater[row][col] != -1:\n",
    "                    continue\n",
    "\n",
    "                isWater[row][col] = depth\n",
    "                q.append((row,col+1))\n",
    "                q.append((row,col-1))\n",
    "                q.append((row-1,col))\n",
    "                q.append((row+1,col))\n",
    "                    \n",
    "            depth += 1\n",
    "\n",
    "        return isWater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        que=[]\n",
    "        res=[[0]*len(isWater[0]) for _ in range(len(isWater))]\n",
    "        visited=[[False]*len(isWater[0]) for _ in range(len(isWater))]\n",
    "        d=((-1,0),(1,0),(0,1),(0,-1))\n",
    "        for i in range(len(isWater)):\n",
    "            for j in range(len(isWater[0])):\n",
    "                if isWater[i][j]==1:\n",
    "                    que.append((i,j))\n",
    "                    visited[i][j]=True\n",
    "        nque=[]\n",
    "        att=0\n",
    "        while que:\n",
    "            i,j=que.pop()\n",
    "            res[i][j]=att\n",
    "            for dx,dy in d:\n",
    "                x=i+dx\n",
    "                y=j+dy\n",
    "                if x<0 or y<0 or x>=len(isWater) or y>=len(isWater[0]) or visited[x][y]:\n",
    "                    continue\n",
    "                nque.append((x,y))\n",
    "                visited[x][y]=True\n",
    "            if len(que)==0:\n",
    "                att+=1\n",
    "                que=nque\n",
    "                nque=[]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "\n",
    "        q = collections.deque()\n",
    "        heights = [[-1]*n for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    q.append((i,j))\n",
    "                    heights[i][j] = 0\n",
    "        \n",
    "        h = 0\n",
    "        while q:\n",
    "            h += 1\n",
    "            length = len(q)\n",
    "            for _ in range(length):\n",
    "                x, y = q.popleft()\n",
    "                for xx, yy in ((x+1,y),(x-1,y),(x,y-1),(x,y+1)):\n",
    "                    if xx < 0 or xx >= m or yy < 0 or yy >= n:\n",
    "                        continue\n",
    "                    if heights[xx][yy] != -1:\n",
    "                        continue\n",
    "                    heights[xx][yy] = h\n",
    "                    q.append((xx,yy))\n",
    "          \n",
    "        return heights\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "        ret = [[0] * n for _ in range(m)]\n",
    "        q = []\n",
    "        vst = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    ret[i][j] = 0\n",
    "                    q.append((i, j))\n",
    "                    vst[i][j] = 1\n",
    "        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))\n",
    "        step = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            step += 1\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in dirs:\n",
    "                    x2, y2 = x + dx, y + dy\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and not vst[x2][y2]:\n",
    "                        vst[x2][y2] = 1\n",
    "                        ret[x2][y2] = step\n",
    "                        q.append((x2, y2))\n",
    "        return ret\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1765 lang=python3\n",
    "#\n",
    "# [1765] 地图中的最高点\n",
    "#\n",
    "# https://leetcode.cn/problems/map-of-highest-peak/description/\n",
    "#\n",
    "# algorithms\n",
    "# Medium (66.35%)\n",
    "# Likes:    121\n",
    "# Dislikes: 0\n",
    "# Total Accepted:    24.8K\n",
    "# Total Submissions: 37.4K\n",
    "# Testcase Example:  '[[0,1],[0,0]]'\n",
    "#\n",
    "# 给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。\n",
    "# \n",
    "# \n",
    "# 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。\n",
    "# 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。\n",
    "# \n",
    "# \n",
    "# 你需要按照如下规则给每个单元格安排高度：\n",
    "# \n",
    "# \n",
    "# 每个格子的高度都必须是非负的。\n",
    "# 如果一个格子是 水域 ，那么它的高度必须为 0 。\n",
    "# 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）\n",
    "# \n",
    "# \n",
    "# 找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。\n",
    "# \n",
    "# 请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个\n",
    "# 。\n",
    "# \n",
    "# \n",
    "# \n",
    "# 示例 1：\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 输入：isWater = [[0,1],[0,0]]\n",
    "# 输出：[[1,0],[2,1]]\n",
    "# 解释：上图展示了给各个格子安排的高度。\n",
    "# 蓝色格子是水域格，绿色格子是陆地格。\n",
    "# \n",
    "# \n",
    "# 示例 2：\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]\n",
    "# 输出：[[1,1,0],[0,1,1],[1,2,2]]\n",
    "# 解释：所有安排方案中，最高可行高度为 2 。\n",
    "# 任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。\n",
    "# \n",
    "# \n",
    "# \n",
    "# \n",
    "# 提示：\n",
    "# \n",
    "# \n",
    "# m == isWater.length\n",
    "# n == isWater[i].length\n",
    "# 1 <= m, n <= 1000\n",
    "# isWater[i][j] 要么是 0 ，要么是 1 。\n",
    "# 至少有 1 个水域格子。\n",
    "# \n",
    "# \n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        h = len(isWater)\n",
    "        w = len(isWater[0])\n",
    "        hight_res = [[-1] * w for _ in range(h)]\n",
    "        queue = []\n",
    "        for i, row in enumerate(isWater):\n",
    "            for j, val in enumerate(row):\n",
    "                if val == 1:\n",
    "                    queue.append((i, j))\n",
    "        def get_neighbor(i, j):\n",
    "            neighbor = set()\n",
    "            direct = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "            for n in direct:\n",
    "                i0 = i + n[0]\n",
    "                j0 = j + n[1]\n",
    "                if 0 <= i0 < h and 0 <= j0 < w:\n",
    "                    if hight_res[i0][j0] == -1:\n",
    "                        neighbor.add((i0, j0))\n",
    "            return neighbor\n",
    "\n",
    "        hight = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in queue:\n",
    "                if hight_res[i[0]][i[1]] == -1:\n",
    "                    hight_res[i[0]][i[1]] = hight\n",
    "                tmp.extend(get_neighbor(*i))\n",
    "            queue = set(tmp)\n",
    "            hight += 1\n",
    "\n",
    "        return hight_res\n",
    "# @lc code=end\n",
    "\n",
    "case1 = [[0,1],[0,0]]\n",
    "case2 = [[0,0,1],[1,0,0],[0,0,0]]\n",
    "if __name__ == '__main__':\n",
    "    Solution().highestPeak(case2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "#         m, n = len(isWater), len(isWater[0])\n",
    "#         d = deque()\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if isWater[i][j] == 1:\n",
    "#                     d.append((i, j, 0))\n",
    "\n",
    "#         vis = set()\n",
    "#         while d:\n",
    "#             i, j, val = d.popleft()\n",
    "#             if (i, j) in vis or i < 0 or i >= m or j < 0 or j >= n:\n",
    "#                 continue\n",
    "#             vis.add((i, j))\n",
    "#             isWater[i][j] = val\n",
    "#             for di, dj in (0, 1),(0,-1),(-1,0),(1,0):\n",
    "#                 ni, nj = i + di, j + dj\n",
    "#                 d.append((ni, nj, val + 1))\n",
    "#         return isWater\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        d = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    d.append((i, j))\n",
    "                isWater[i][j] -= 1\n",
    "\n",
    "        while d:\n",
    "            i, j = d.popleft()\n",
    "            for di, dj in (0, 1),(0,-1),(-1,0),(1,0):\n",
    "                ni, nj = i + di, j + dj\n",
    "                if ni < 0 or ni >= m or nj < 0 or nj >= n or isWater[ni][nj] != -1:\n",
    "                    continue\n",
    "                isWater[ni][nj] = isWater[i][j] + 1\n",
    "            \n",
    "                d.append((ni, nj))\n",
    "        return isWater\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(isWater), len(isWater[0])\n",
    "        q = deque()\n",
    "        visit = [[False] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if isWater[i][j] == 0:\n",
    "                    isWater[i][j] = 1\n",
    "                else:\n",
    "                    visit[i][j] = True\n",
    "                    isWater[i][j] = 0\n",
    "                    q.append([i, j])\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:\n",
    "                    visit[nx][ny] = True\n",
    "                    q.append([nx, ny])\n",
    "                    isWater[nx][ny] = isWater[x][y] + 1\n",
    "        return isWater "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(isWater), len(isWater[0])\n",
    "        orientation = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        CONSTANT = 4\n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            for k in range(m):\n",
    "                if isWater[i][k] == 0:\n",
    "                    isWater[i][k] = 1\n",
    "                else:\n",
    "                    q.append((i, k, 0))\n",
    "                    isWater[i][k] = 0\n",
    "        mp = copy.deepcopy(isWater)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            for j in range(CONSTANT):\n",
    "                tmp1 = tmp[0] + orientation[j][0]\n",
    "                tmp2 = tmp[1] + orientation[j][1]\n",
    "                if 0 <= tmp1 < n and 0 <= tmp2 < m and mp[tmp1][tmp2]:\n",
    "                    mp[tmp1][tmp2] = 0\n",
    "                    isWater[tmp1][tmp2] = tmp[2] + 1\n",
    "                    q.append((tmp1, tmp2, tmp[2] + 1))\n",
    "        return isWater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(isWater), len(isWater[0])\n",
    "        orientation = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        CONSTANT = 4\n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            for k in range(m):\n",
    "                if isWater[i][k] == 0:\n",
    "                    isWater[i][k] = 1\n",
    "                else:\n",
    "                    q.append((i, k, 0))\n",
    "                    isWater[i][k] = 0\n",
    "        mp = copy.deepcopy(isWater)\n",
    "        tmp, tmp1, tmp2 = None, None, None\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            for j in range(CONSTANT):\n",
    "                tmp1 = tmp[0] + orientation[j][0]\n",
    "                tmp2 = tmp[1] + orientation[j][1]\n",
    "                if tmp1 >= 0 and tmp1 < n and tmp2 >= 0 and tmp2 < m and mp[tmp1][tmp2]:\n",
    "                    mp[tmp1][tmp2] = 0\n",
    "                    isWater[tmp1][tmp2] = tmp[2] + 1\n",
    "                    q.append((tmp1, tmp2, tmp[2] + 1))\n",
    "        return isWater"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "        height = [[-1] * n for _ in range(m)]\n",
    "        queue = deque([(x, y) for x in range(m) for y in range(n) if isWater[x][y] == 1])\n",
    "        for x, y in queue:\n",
    "            height[x][y] = 0\n",
    "\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for i, j in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and height[i][j] == -1:\n",
    "                        height[i][j] = depth + 1\n",
    "                        queue.append((i, j))\n",
    "            depth += 1\n",
    "        return height\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "    m = len(isWater)\n",
    "    n = len(isWater[0])\n",
    "    result = [[-1] * n for _ in range(m)]\n",
    "    water = deque() # 用 deque效率提升100倍\n",
    "    for i in range(m):\n",
    "      for j in range(n):\n",
    "        if isWater[i][j] == 1:\n",
    "          water.append([i,j])\n",
    "          result[i][j]=0\n",
    "    while water:\n",
    "      x,y=water.popleft()\n",
    "      nn = result[x][y]+1\n",
    "      if x-1 >=0 and result[x-1][y] == -1:\n",
    "        water.append([x-1,y])\n",
    "        result[x-1][y]= nn\n",
    "      if y-1 >=0 and result[x][y-1] == -1:\n",
    "        water.append([x,y-1])\n",
    "        result[x][y-1]= nn\n",
    "      if x+1 < m and result[x+1][y] == -1:  \n",
    "        water.append([x+1,y])\n",
    "        result[x+1][y]= nn\n",
    "      if y+1 < n and result[x][y+1] == -1:\n",
    "        water.append([x,y+1])\n",
    "        result[x][y+1]= nn\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        # 广度优先搜索 -- 超时\n",
    "        # 多源广度优先搜索？\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        height = [[0x3f3f3f]*n for _ in range(m)]\n",
    "        sea = deque()\n",
    "        visited = list()\n",
    "\n",
    "        def bfs(i,j):\n",
    "            dir = [[0,1],[0,-1],[-1,0],[1,0]]\n",
    "            for dx,dy in dir:\n",
    "                if i+dx<0 or i+dx>=m or j+dy<0 or j+dy>=n or height[i+dx][j+dy]!=0x3f3f3f:\n",
    "                    continue\n",
    "                else:\n",
    "                    #height[i+dx][j+dy] = min(height[i+dx][j+dy],height[i][j]+1)\n",
    "                    height[i+dx][j+dy] = height[i][j]+1\n",
    "                    #visited.append([i+dx,j+dy])\n",
    "                    sea.append([i+dx,j+dy])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    height[i][j] = 0\n",
    "                    sea.append([i,j])\n",
    "                    #visited.append([i,j])\n",
    "        while(sea):\n",
    "            i,j = sea.popleft()\n",
    "            bfs(i,j)\n",
    "        return height\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        dp = [[10**9]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i > 0:\n",
    "                        dp[i][j] = min(dp[i][j],dp[i-1][j] + 1)\n",
    "                    if j > 0:\n",
    "                        dp[i][j] = min(dp[i][j],dp[i][j-1] + 1)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if isWater[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i < m-1:\n",
    "                        dp[i][j] = min(dp[i][j],dp[i+1][j] + 1)\n",
    "                    if j < n-1:\n",
    "                        dp[i][j] = min(dp[i][j],dp[i][j+1] + 1)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(isWater),len(isWater[0])\n",
    "        g=[[-1]*n for _ in range(m)]\n",
    "        que=deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]==1:\n",
    "                    que.append([i,j])\n",
    "                    g[i][j]=0\n",
    "        while que:\n",
    "            x,y=que.popleft()\n",
    "            for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                if 0<=nx<m and 0<=ny<n and g[nx][ny]==-1:\n",
    "                    g[nx][ny]=g[x][y]+1\n",
    "                    que.append([nx,ny])\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "    m = len(isWater)\n",
    "    n = len(isWater[0])\n",
    "    result = [[-1] * n for _ in range(m)]\n",
    "    count = 0\n",
    "    h = 0\n",
    "    water=[]\n",
    "    for i in range(m):\n",
    "      for j in range(n):\n",
    "        if isWater[i][j] == 1:\n",
    "          water.append([i,j])\n",
    "          result[i][j]=0\n",
    "          count = count + 1\n",
    "    if len(water)>m * n/10:\n",
    "      while count < m * n:\n",
    "          for i in range(m):\n",
    "              for j in range(n):\n",
    "                  if result[i][j] == -1:\n",
    "                      min = h\n",
    "                      for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                          if 0 <= x < m and 0 <= y < n and result[x][y] != -1 and result[x][y] < min:\n",
    "                              min = result[x][y]\n",
    "                      if min < h:\n",
    "                          result[i][j] = min + 1\n",
    "                          count = count + 1\n",
    "          h = h + 1\n",
    "    else:\n",
    "      while water:\n",
    "        x,y=water.pop(0)\n",
    "        nn = result[x][y]+1\n",
    "        if x-1 >=0 and result[x-1][y] == -1:\n",
    "          water.append([x-1,y])\n",
    "          result[x-1][y]= nn\n",
    "        if y-1 >=0 and result[x][y-1] == -1:\n",
    "          water.append([x,y-1])\n",
    "          result[x][y-1]= nn\n",
    "        if x+1 < m and result[x+1][y] == -1:  \n",
    "          water.append([x+1,y])\n",
    "          result[x+1][y]= nn\n",
    "        if y+1 < n and result[x][y+1] == -1:\n",
    "          water.append([x,y+1])\n",
    "          result[x][y+1]= nn\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        # 多元bfs,因为一个点最终的高度取决于离他最近的水（相邻高度差1，从水往这个点高度逐渐加1，最近距离就是该店高度），因此从所有水域出发左多元bsf填点即可\n",
    "        q=collections.deque()\n",
    "        m,n=len(isWater),len(isWater[0])\n",
    "        grid=[[inf]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]==1:\n",
    "                    q.append((i,j))\n",
    "                    grid[i][j]=0 \n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for di,dj in (-1,0),(1,0),(0,-1),(0,1):\n",
    "                ni,nj=i+di,j+dj \n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj]>grid[i][j]+1:\n",
    "                    grid[ni][nj]=grid[i][j]+1\n",
    "                    q.append((ni,nj))\n",
    "        return grid\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        height = [[0] * n for _ in range(m)]\n",
    "        queue = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 把水域放进队列\n",
    "                if isWater[i][j] == 1:\n",
    "                    queue.appendleft((i, j))\n",
    "                # 陆地记为 -1\n",
    "                height[i][j] = isWater[i][j] - 1\n",
    "        while queue:\n",
    "            i, j = queue.pop()\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                if 0 <= x < m and 0 <= y < n and height[x][y] == -1:\n",
    "                    height[x][y] = height[i][j] + 1\n",
    "                    queue.appendleft((x, y))\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        height = [[0] * n for _ in range(m)]\n",
    "        queue = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 把水域放进队列\n",
    "                if isWater[i][j] == 1:\n",
    "                    queue.appendleft((i, j))\n",
    "                # 陆地记为 -1\n",
    "                height[i][j] = isWater[i][j] - 1\n",
    "        while queue:\n",
    "            i, j = queue.pop()\n",
    "            # 访问当前节点的周围（一开始是水域的周围）\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                # 把还没访问过的节点放进queue，然后把高度+1\n",
    "                if 0 <= x < m and 0 <= y < n and height[x][y] == -1:\n",
    "                    height[x][y] = height[i][j] + 1\n",
    "                    queue.appendleft((x, y))\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        dq = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j]:\n",
    "                    dq.append((i, j))\n",
    "                    ans[i][j] = 0\n",
    "        \n",
    "        while dq:\n",
    "            a, b = dq.popleft()\n",
    "            h = ans[a][b]\n",
    "            for x, y in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = h+1\n",
    "                    dq.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        c = [[-1 for _ in range(m)] for _ in range(n)]\n",
    "        q = deque()\n",
    "        #vis = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j]:\n",
    "                    c[i][j] = 0\n",
    "                    q.append([i,j])\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                nx,ny = x + dx,y + dy\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m or c[nx][ny] != -1:\n",
    "                    continue\n",
    "                c[nx][ny] = 1 + c[x][y]\n",
    "                q.append([nx,ny])\n",
    "        \n",
    "        return c\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)  # 将所有水域入队\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)  # 将所有水域入队\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        height = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        q = deque()\n",
    "        \n",
    "        # 初始化水域的高度为0，并将它们添加到队列中\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    height[i][j] = 0\n",
    "                    q.append((i, j))\n",
    "        \n",
    "        # 用于找到所有相邻格子的方向\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # 执行BFS\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                # 检查新位置是否在界内，并且是否被访问过\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and height[new_x][new_y] == -1:\n",
    "                    height[new_x][new_y] = height[x][y] + 1\n",
    "                    q.append((new_x, new_y))\n",
    "        \n",
    "        return height\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        res = [[isWater[i][j]-1 for j in range(n)] for i in range(m)]\n",
    "        queue = deque((i, j) for j in range(n) for i in range(m) if res[i][j] == 0)\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                if 0 <= x < m and 0 <= y < n and res[x][y] == -1:\n",
    "                    res[x][y] = res[i][j] + 1\n",
    "                    queue.append((x, y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        n,m = len(isWater),len(isWater[0])\n",
    "        height = [[0 for i in range(m)] for i in range(n)]\n",
    "        dir_ = {(1,0),(0,1),(0,-1),(-1,0)}\n",
    "        water = set()\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if isWater[i][j]:\n",
    "                    water.add((i,j))\n",
    "                    queue.append((i,j))\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            for dx,dy in dir_:\n",
    "                if x + dx < 0 or x + dx >= n or y + dy < 0 or y + dy >= m or (x + dx,y + dy) in water or ((x + dx,y + dy) not in water and height[x + dx][y + dy]):\n",
    "                    continue\n",
    "                height[x + dx][y + dy] = height[x][y] + 1\n",
    "                queue.append((x + dx,y + dy))\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        res = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i,j) for i,row in enumerate(isWater) for j,water in enumerate(row)  if water)\n",
    "       \n",
    "        dirs = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            for i,j in dirs:\n",
    "                if 0<=x+i<m and 0<=y+j<n and  res[x+i][y+j]==-1:\n",
    "                    res[x+i][y+j]=res[x][y]+1\n",
    "                    q.append((x+i,y+j))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "#         m, n = len(isWater), len(isWater[0])\n",
    "#         res = [[-1 for col in row] for row in isWater]\n",
    "#         q = deque() \n",
    "#         for i, row in enumerate(isWater): \n",
    "#             for j, col in enumerate(row):\n",
    "#                 if col == 1:\n",
    "#                     q.append((i,j))\n",
    "#                     res[i][j] = 0\n",
    "\n",
    "#         while q:\n",
    "#             i, j = q.popleft()\n",
    "#             for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "#                 if 0 <= x < m and 0 <= y < n and res[x][y] == -1:\n",
    "#                     res[x][y] = res[i][j] + 1\n",
    "#                     q.append((x, y))\n",
    "\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        题目要求：按照规则返回最大高度方案的格子高度矩阵，水域高度默认为0，相邻格子(上下左右)高度差最多为1，高度非负\n",
    "        :param isWater: 大小为 m x n 的整数矩阵，0代表陆地，1代表水域\n",
    "        :return: 返回满足最大高度方案的格子高度矩阵\n",
    "        \"\"\"\n",
    "        # 解题思路：题目很容易理解，很自然就想到了BFS(这个月好多次了)，要想最大高度尽可能的大，那么让每个格子都最大(稍微用点贪心)\n",
    "        # 题目已知水域高度为1，那么就从水域开始遍历，其相邻格子最大高度显然为1\n",
    "        # 然后，计算与高度为1的格子相邻的、尚未被遍历过的格子的高度。对于这些格子来说最大高度为2，以此类推\n",
    "        # 上述过程就是从水域出发，执行广度优先搜索的过程。因此，记录下所有水域的位置，然后执行广度优先搜索，计算出所有陆地格子的高度，即为答案\n",
    "        m, n = len(isWater), len(isWater[0])  # 取到m,n\n",
    "        ans = [[water - 1 for water in row] for row in isWater]  # 初始化高度矩阵(0代表陆地，1代表水域，故初始时水域高度为0，陆地为-1)\n",
    "        # print(ans)\n",
    "        # 这里用高度为-1标记有没有遍历过即可，因为高度更新后必不为-1了，不用再专门用标记集合了，算是个小技巧\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)  # 将所有水域入队\n",
    "        print(q)\n",
    "        # 后面又是BFS的套路模板了\n",
    "        while q:\n",
    "            i, j = q.popleft()  # 取出队头坐标\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):  # 遍历相邻格子\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:  # 不越界，没遍历过的陆地才遍历\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)\n",
    "\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "#         m, n = len(isWater), len(isWater[0])\n",
    "#         ans = [[water - 1 for water in row] for row in isWater]\n",
    "#         q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)\n",
    "        \n",
    "#         while q:\n",
    "#             i, j = q.popleft()\n",
    "#             for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "#                 if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "#                     ans[x][y] = ans[i][j] + 1\n",
    "#                     q.append((x, y))\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]    #答案\n",
    "\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)   #水域入队列\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(isWater)\n",
    "        m = len(isWater[0])\n",
    "\n",
    "        res = [[tmp - 1 for tmp in row] for row in isWater]\n",
    "        queue = deque((x, y) for x, row in enumerate(isWater) for y, water in enumerate(row) if water)\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= i < n and 0 <= j < m and res[i][j] == -1:\n",
    "                    res[i][j] = res[x][y] + 1\n",
    "                    queue.append((i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)  # 将所有水域入队\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[water - 1 for water in row] for row in isWater]\n",
    "\n",
    "        q = deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:\n",
    "                    ans[x][y] = ans[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "\n",
    "        if m == 0 or n == 0:\n",
    "            return isWater\n",
    "        \n",
    "        heights = [[value - 1 for value in row] for row in isWater]\n",
    "\n",
    "        pending_list = deque()\n",
    "        for i, row in enumerate(heights):\n",
    "            for j, value in enumerate(row):\n",
    "                if value == 0:\n",
    "                    pending_list.append((i,j))\n",
    "\n",
    "        while pending_list:\n",
    "            i, j = pending_list.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and heights[x][y] == -1:\n",
    "                    heights[x][y] = heights[i][j] + 1\n",
    "                    pending_list.append((x,y))\n",
    "\n",
    "        return heights\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        ans = [[j - 1 for j in i] for i in isWater]\n",
    "        queue = deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1: queue.append((i, j))\n",
    "\n",
    "        while queue:\n",
    "            i, j = queue.popleft()\n",
    "            for a, b in ((i - 1, j), (i + 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if 0 <= a < m and 0 <= b < n and ans[a][b] == -1:\n",
    "                    ans[a][b] = ans[i][j] + 1\n",
    "                    queue.append((a, b))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m, n, result, q = len(isWater), len(isWater[0]), [[water - 1 for water in row] for row in isWater], deque((i, j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water)\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if -1 < x < m and -1 < y < n and result[x][y] == -1:\n",
    "                    result[x][y] = result[i][j] + 1\n",
    "                    q.append((x, y))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        m,n = len(isWater),len(isWater[0])\n",
    "        ans = [[water -1 for water in row] for row in isWater]\n",
    "        q = deque((i,j) for i, row in enumerate(isWater) for j,water in enumerate(row) if water)\n",
    "        while q:\n",
    "            i,j = q.popleft()\n",
    "            for x,y in ((i-1,j),(i+1,j),(i,j+1),(i,j-1)):\n",
    "                if 0 <= x < m and 0 <= y <n and ans[x][y] == -1:\n",
    "                    ans[x][y] =ans[i][j]+1\n",
    "                    q.append((x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        rows = len(isWater)\n",
    "        cols = len(isWater[0])\n",
    "        visted = [[0] * cols for _ in range(rows)]\n",
    "\n",
    "        res = [[-1] * cols for _ in range(rows)]\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if isWater[i][j] == 1:\n",
    "                    res[i][j] = 0\n",
    "                    queue.append([i, j])\n",
    "                    visted[i][j] = 1\n",
    "\n",
    "        while queue:\n",
    "            [i, j] = queue.popleft()\n",
    "            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                if 0 <= x < rows and 0 <= y <cols and not visted[x][y]:\n",
    "                    res[x][y] = res[i][j] + 1\n",
    "                    visted[x][y] = 1\n",
    "                    queue.append([x, y])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        height = [[0] * len(isWater[0]) for _ in range(len(isWater))]\n",
    "        visit = [[False] * len(isWater[0]) for _ in range(len(isWater))]\n",
    "\n",
    "        q = deque()\n",
    "        level = 0\n",
    "        directions = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        for i in range(len(isWater)):\n",
    "            for j in range(len(isWater[0])):\n",
    "                if isWater[i][j] == 1:\n",
    "                    q.append([i,j])\n",
    "        \n",
    "        while q:\n",
    "            level += 1\n",
    "            for i in range(len(q)):\n",
    "                m = q.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    x = m[0] + dx\n",
    "                    y = m[1] + dy\n",
    "                    if 0 <= x < len(isWater) and 0 <= y <len(isWater[0]) and isWater[x][y] == 0 and not visit[x][y]:\n",
    "                        height[x][y] = max(height[x][y], height[m[0]][m[1]]+1)\n",
    "                        visit[x][y] = True\n",
    "                        q.append([x,y])\n",
    "        \n",
    "        return height\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def highestPeak(self, isWater):\n",
    "        waitlist=collections.deque()\n",
    "        move = [[0,1],[1,0],[-1,0],[0,-1]]\n",
    "        b =[[0 for j in range(len(isWater[0]))]for i in range(len(isWater))]\n",
    "        map1 = [[0 for j in range(len(isWater[0]))]for i in range(len(isWater))]\n",
    "        for i in range(len(isWater)):\n",
    "            for j in range(len(isWater[0])):\n",
    "                if isWater[i][j]==1:\n",
    "                    b[i][j]=1\n",
    "                    waitlist.append((i,j))\n",
    "        while waitlist:\n",
    "            x,y =waitlist.popleft()\n",
    "            for i in range(4):\n",
    "                if x+move[i][0] in range(len(isWater)) and y+move[i][1] in range(len(isWater[0])) and b[x+move[i][0]][y+move[i][1]]==0:\n",
    "                    waitlist.append((x+move[i][0],y+move[i][1]))\n",
    "                    b[x+move[i][0]][y+move[i][1]]=1\n",
    "                    map1[x+move[i][0]][y+move[i][1]] = map1[x][y]+1\n",
    "        return map1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dr = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        vis = set()\n",
    "\n",
    "        m = len(isWater)\n",
    "        n = len(isWater[0])\n",
    "\n",
    "        q = []\n",
    "        nq = []\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    q.append(i * m + j)\n",
    "        \n",
    "        lvl = 0\n",
    "        while q or nq:\n",
    "            if not q:\n",
    "                q = nq\n",
    "                nq = []\n",
    "                lvl += 1\n",
    "            \n",
    "            curr = q.pop()\n",
    "            if curr in vis:\n",
    "                continue\n",
    "            vis.add(curr)\n",
    "\n",
    "            nowx, nowy = curr // m, curr % m\n",
    "            res[nowx][nowy] = lvl\n",
    "            \n",
    "\n",
    "            for d in dr:\n",
    "                tmpx = nowx + d[0]\n",
    "                tmpy = nowy + d[1]\n",
    "\n",
    "                if 0 <= tmpx < m and 0 <= tmpy < n:\n",
    "                    nq.append(tmpx * m + tmpy)\n",
    "\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        # 多源bfs\n",
    "        m, n = len(isWater), len(isWater[0])\n",
    "        cur = [(i, j) for i in range(m) for j in range(n) if isWater[i][j] == 1]\n",
    "        vis = set(cur)\n",
    "\n",
    "        step = 0\n",
    "        ans = [[0 for j in range(n)] for i in range(m)]\n",
    "        while cur:\n",
    "            nxt = set()\n",
    "            for x, y in cur:\n",
    "                ans[x][y] = step\n",
    "                for u, v in (x+1, y), (x-1, y), (x, y+1), (x, y-1):\n",
    "                    if 0 <= u < m and 0 <= v < n and (u, v) not in vis:\n",
    "                        vis.add((u, v))\n",
    "                        nxt.add((u, v))\n",
    "            cur = list(nxt)\n",
    "            step += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:\n",
    "        #max_gap:1\n",
    "        # bfs求到达边界时的max_len\n",
    "        max_len = 0\n",
    "        q = deque()\n",
    "        m,n = len(isWater), len(isWater[0])\n",
    "        vis = set()\n",
    "        grid = [[-1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if isWater[i][j] == 1:\n",
    "                    q.append((i,j))\n",
    "                    grid[i][j] = 0\n",
    "                    vis.add((i,j))\n",
    "\n",
    "        \n",
    "        step = 0\n",
    "        dirs = [[-1,0], [1,0], [0,1], [0,-1]]\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                i,j = q.popleft()\n",
    "                #vis.add((i,j)) #可以不用这个\n",
    "                for d1,d2 in dirs:\n",
    "                    x,y = i+d1, j+d2\n",
    "                    if 0<=x<m and 0<=y<n and (x,y) not in vis: #未访问过的陆地\n",
    "                        q.append((x,y))\n",
    "                        grid[x][y] = step \n",
    "                        vis.add((x,y))\n",
    "\n",
    "        return grid\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
